import java.util.HashMap;
import java.util.Map;

/**
 * @author 雷明浩
 * @date 2025/5/29 11:45
 */
public class LRUCache {
    // leetcode LRU Cache
    // https://leetcode.cn/problems/lru-cache/description/?envType=study-plan-v2&envId=top-100-liked
    class DLNode {
        public int key;
        public int value;
        public DLNode prev;
        public DLNode next;
        public DLNode() {};
        public DLNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private int capacity;
    private Map<Integer, DLNode> cache;
    private DLNode head;
    private DLNode tail;
    private int size;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>();
        head = new DLNode();
        tail = new DLNode();
        head.next = tail;;
        tail.prev = head;
        this.size = 0;
    }

    public int get(int key) {
        DLNode node = cache.get(key);
        if (node == null) {
            return -1;
        }else {
            removeNode(node);
            moveToHead(node);
        }
        return node.value;
    }

    public void put(int key, int value) {
        DLNode node = cache.get(key);
        if (node != null) {
            node.value = value;
            removeNode(node);
            moveToHead(node);
        }else {
            DLNode newNode = new DLNode(key, value);
            cache.put(key, newNode);
            newNode.next = head.next;
            head.next.prev = newNode;
            head.next = newNode;
            newNode.prev = head;
            this.size++;
            if (this.size > this.capacity) {
                cache.remove(tail.prev.key);
                removeNode(tail.prev);
                this.size--;
            }
        }
    }

    private void removeNode(DLNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(DLNode node) {
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
        node.prev = head;
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(2, 1);
        cache.put(1, 1);
        cache.put(2, 3);
        cache.put(4, 1);
        System.out.println(cache.get(1));
        System.out.println(cache.get(2));
    }
}